#include "algorithm_sequential.h"


/** Resi sekvencnim algoritmem zadanou mapu.
 * \return true, pokud se povedlo vytvorit korektni prirazeni frekvenci
 */
bool SequentialAlgorithm::Solve() {
	/* Jednoduchy algoritmus - rozumne setridim seznam vysilacu
		- pak vzdy vyberu jeden a priradim mu frekvenci
	*/

	CallList * call_list;
	int * ordering;

	frequencies = area->getMaxFrequencies();
	options->Display(GetDetail());

	// next channel selection
	switch (options->next) {
		case Sequential:
			call_list = new CallList(area, frequencies);
			break;
		case GSD:
			call_list = new GSDCallList(area, frequencies);
			break;
		default:
			options->Log() << "Error: Unknown algorithm for next transmitter selection!";
			return false;
	}

	// order the antenas according to the initial ordering type
	timer->start();
	switch (options->ordering) {
		case LargestFirst:
			ordering = orderLargestFirst();
			break;
		case LargestFirstExclude:
			ordering = orderLargestFirstExclude();
			break;
		case SmallestLast:
			ordering = orderSmallestLast();
			break;
		case GLargestFirst:
			ordering = orderGLargestFirst();
			break;
		case GLargestFirstExclude:
			ordering = orderGLargestFirstExclude();
			break;
		case GSmallestLast:
			ordering = orderGSmallestLast();
			break;
		case Random:
			ordering = orderRandom();
			break;
		default:
			options->Log() << "ERROR: Unknown initial ordering!";
			delete call_list;
			return false;
	}

	call_list->initialize(ordering);

	// run the assignment algorithm
	switch (options->frequency) {
		case Smallest:
			frequencySmallest(call_list);
			break;
		case Occupied:
			frequencyOccupied(call_list);
			break;
		case SmallestOccupied:
			frequencySmallestOccupied(call_list);
			break;
		case HeaviestOccupied:
			frequencyHeaviestOccupied(call_list);
			break;
		default:
			options->Log() << "ERROR: Unknown algorithm for next frequency assignment!";
			delete call_list;
			delete ordering;
			return false;
	}

	frequencies = call_list->getSpan();
	options->Log() << "Total time: " << timer->stop() << std::endl;
	delete call_list;
	delete ordering;
	return true;
}


// The degree is the number of neighbours in the constraint graph
/** Spocita stupne vsem vysilacum. Stupen je pocet podminek, ktere vysilac porusuje.
 */
void SequentialAlgorithm::CountDegrees() {
	for (int i = 0; i < area->CELLS_CNT; ++i) {
		area->cells[i].info = -1; // delete my constraint with myself
		for (std::vector<int>::const_iterator n = area->cells[i].constraints.begin();
		n != area->cells[i].constraints.end(); ++n) {
			area->cells[i].info += area->cells[*n].demand;
		}
	}
}

// The degree is the weighted sum of the constraint edges
/** Spocita vazene stupne vsem vysilacum. Vazeny stupen je soucet vah vsech vysilacem porusenych podminek.
 */
void SequentialAlgorithm::GCountDegrees() {
	for (int i = 0; i < area->CELLS_CNT; ++i) {
		area->cells[i].info = -area->frequencyDistance(i, i); // my own constraint
			for (std::vector<int>::const_iterator n = area->cells[i].constraints.begin();
			n != area->cells[i].constraints.end(); ++n) {
				area->cells[i].info += area->cells[*n].demand * area->frequencyDistance(i, *n);
		}
	}
}

/** Vraci vysilac s nejmensim stupnem.
 * \return iterator na vysilac
 */
std::list<int>::iterator SequentialAlgorithm::mmin_element(std::list<int>::iterator begin, std::list<int>::iterator end) {
	std::list<int>::iterator min = begin;
	for (std::list<int>::iterator i = begin; i != end; ++i) {
		if (degreeComparer(*i, *min)) min = i;
	}
	return min;
}

/** Vraci vysilac s nejvetsim stupnem.
 * \return iterator na vysilac
 */
std::list<int>::iterator SequentialAlgorithm::mmax_element(std::list<int>::iterator begin, std::list<int>::iterator end) {
	std::list<int>::iterator max = begin;
	for (std::list<int>::iterator i = begin; i != end; ++i) {
		if (!degreeComparer(*i, *max)) max = i;
	}
	return max;
}


/* INITIAL ORDERINGS */

// Largest degree first
/** Prvotni setrideni podle stupne. 
 */
int * SequentialAlgorithm::orderLargestFirst() {
	int * call_list = new int[area->size];
	CountDegrees();
	std::multimap<int, int> degrees;
	for (int j = 0; j < area->CELLS_CNT; ++j) {
		for (int i = 0; i < area->cells[j].demand; ++i) {
			degrees.insert(std::pair<int, int>(area->cells[j].info, area->cells[j].index + i));
		}
	}
	int call = 0;
	int count = degrees.size();
	for (std::multimap<int, int>::const_iterator i = degrees.begin(); i != degrees.end(); ++i) {
		call_list[count - ++call] = i->second;
	}
	return call_list;
}

// Largest degree first excluding used constraints
/** Prvotni setrideni podle stupne s vypoustenim (podminky porusene se zarazymivrcholy nejsou uvazovany).
 */
int * SequentialAlgorithm::orderLargestFirstExclude() {
	int * call_list = new int[area->size];
	CountDegrees();
	std::list<int> calls;
	for (int i = 0; i < area->size; ++i) {
		calls.push_back(i);
	}
	for (int i = 0; i < area->size && !calls.empty(); ++i) {
		// find the antena with the most constraints
		std::list<int>::iterator max;
		max = mmax_element(calls.begin(), calls.end());
		call_list[i] = *max;
		// delete the constraints antena made in the graph
		int cell = area->findCell(*max);
		for (std::vector<int>::const_iterator n = area->cells[cell].constraints.begin();
			n != area->cells[cell].constraints.end(); ++n) {
				--area->cells[*n].info;
		}
		// erase the antena from the list
		calls.erase(max);
	}
	return call_list;
}

// Smallest degree last excluding used constraints
/** Nejmensi stupen na konec.
 */
int * SequentialAlgorithm::orderSmallestLast() {
	int * call_list = new int[area->size];
	CountDegrees();
	std::list<int> calls;
	for (int i = 0; i < area->size; ++i) {
		calls.push_back(i);
	}
	for (int i = area->size - 1; i >= 0 && !calls.empty(); --i) {
		// find the antena with the most constraints
		std::list<int>::iterator min;
		min = mmin_element(calls.begin(), calls.end());
		call_list[i] = *min;
		// delete the constraints antena made in the graph
		int cell = area->findCell(*min);
		for (std::vector<int>::const_iterator n = area->cells[cell].constraints.begin();
			n != area->cells[cell].constraints.end(); ++n) {
				--area->cells[*n].info;
		}
		// erase the antena from the list
		calls.erase(min);
	}
	return call_list;
}

/* GENERALIZED INITIAL ORDERINGS */

// Generalized largest degree first
/** Prvotni setrideni podle vazeneho stupne.
 */
int * SequentialAlgorithm::orderGLargestFirst() {
	int * call_list = new int[area->size];
	GCountDegrees();
	std::multimap<int, int> degrees;
	for (int j = 0; j < area->CELLS_CNT; ++j) {
		for (int i = 0; i < area->cells[j].demand; ++i) {
			degrees.insert(std::pair<int, int>(area->cells[j].info, area->cells[j].index + i));
		}
	}
	int call = 0;
	int count = degrees.size();
	for (std::multimap<int, int>::const_iterator i = degrees.begin(); i != degrees.end(); ++i) {
		call_list[count - ++call] = i->second;
	}
	return call_list;
}

// Generalized largest degree first excluding the used constraints
/** Prvotni setrideni podle vazeneho stupne s vypoustenim
 */
int * SequentialAlgorithm::orderGLargestFirstExclude() {
	int * call_list = new int[area->size];
	GCountDegrees();
	std::list<int> calls;
	for (int i = 0; i < area->size; ++i) {
		calls.push_back(i);
	}
	for (int i = 0; i < area->size && !calls.empty(); ++i) {
		// find the antena with the most constraints
		std::list<int>::iterator max;
		max = mmax_element(calls.begin(), calls.end());
		call_list[i] = *max;
		// delete the constraints antena made in the graph
		int cell = area->findCell(*max);
		for (std::vector<int>::const_iterator n = area->cells[cell].constraints.begin();
			n != area->cells[cell].constraints.end(); ++n) {
				area->cells[*n].info -= area->frequencyDistance(cell, *n);
		}
		// erase the antena from the list
		calls.erase(max);
	}
	return call_list;
}

// Generalized smallest degree last excluding the used constraints
/** Nejmensi vazeny stupen na konec.
 */
int * SequentialAlgorithm::orderGSmallestLast() {
	int * call_list = new int[area->size];
	GCountDegrees();
	std::list<int> calls;
	for (int i = 0; i < area->size; ++i) {
		calls.push_back(i);
	}
	for (int i = area->size - 1; i >= 0 && !calls.empty(); --i) {
		// find the antena with the most constraints
		std::list<int>::iterator min;
		min = mmin_element(calls.begin(), calls.end());
		call_list[i] = *min;
		// delete the constraints antena made in the graph
		int cell = area->findCell(*min);
		for (std::vector<int>::const_iterator n = area->cells[cell].constraints.begin();
			n != area->cells[cell].constraints.end(); ++n) {
				area->cells[*n].info -= area->frequencyDistance(cell, *n);
		}
		// erase the antena from the list
		calls.erase(min);
	}
	return call_list;
}

// Random order
/** Nahodne setrideni.
 */
int * SequentialAlgorithm::orderRandom() {
	int * call_list = new int[area->size];
	bool * used = new bool[area->size];
	for (int i = 0; i < area->size; ++i) {
		used[i] = false;
	}
	for (int i = 0; i < area->size; ++i) {
		int r = rand() % area->size;
		while (used[r]) {
			r = rand() % area->size;
		}
		call_list[i] = r;
		used[r] = true;
	}
	return call_list;
}


/* FREQUENCY ASSIGNMENT */

// Smallest acceptable frequency
/** Vyber nejmensi dostupne frekvence.
 * \param call_list setrideny seznam vysilacu
 */
void SequentialAlgorithm::frequencySmallest(CallList * call_list) {
	while (call_list->getNext()) {
		options->Log() << std::setw(5) << call_list->getCurrent() << "=";
		bool fail = true;
		int cell = area->findCell(call_list->getCurrent());
		for (int f = 1; f <= frequencies; ++f) {
			if (area->assignCall(call_list->getCurrent(), f, cell)) {
				call_list->assign(f);
				fail = false;
				break;
			}
		}
		options->Log() << area->calls[call_list->getCurrent()];
	}
	options->Log() << std::endl;
}

// Acceptable occupied frequency
/** Vyber nahodne z jiz pouzitych frekvenci.
 * \param call_list setrideny seznam vysilacu
 */
void SequentialAlgorithm::frequencyOccupied(CallList * call_list) {
	std::list<int> occupied;
	while (call_list->getNext()) {
		options->Log() << std::setw(5) << call_list->getCurrent() << "=";
		bool fail = true;
		int cell = area->findCell(call_list->getCurrent());
		/* try to assign occupied frequency */
		for (std::list<int>::const_iterator f = occupied.begin(); f != occupied.end(); ++f) {
			if (area->assignCall(call_list->getCurrent(), *f, cell)) {
				call_list->assign(*f);
				fail = false;
				break;
			}
		}
		/* if no occupied frequency available, assign the smallest acceptable */
		if (fail) {
			for (int f = 1; f <= frequencies; ++f) {
				if (area->assignCall(call_list->getCurrent(), f, cell)) {
					call_list->assign(f);
					fail = false;
					occupied.push_back(f);
					break;
				}
			}
		}
		options->Log() << area->calls[call_list->getCurrent()];
	}
	options->Log() << std::endl;
}

// Smallest acceptable occupied frequency
/** Vyber nejmensi z jiz pouzitych frekvenci.
 * \param call_list setrideny seznam vysilacu
 */
void SequentialAlgorithm::frequencySmallestOccupied(CallList * call_list) {
	std::set<int> occupied;
	while (call_list->getNext()) {
		options->Log() << std::setw(5) << call_list->getCurrent() << "=";
		bool fail = true;
		int cell = area->findCell(call_list->getCurrent());
		/* try to assign occupied frequency */
		for (std::set<int>::const_iterator f = occupied.begin(); f != occupied.end(); ++f) {
			if (area->assignCall(call_list->getCurrent(), *f, cell)) {
				call_list->assign(*f);
				fail = false;
				break;
			}
		}
		/* if no occupied frequency available, assign the smallest acceptable */
		if (fail) {
			for (int f = 1; f <= frequencies; ++f) {
				if (area->assignCall(call_list->getCurrent(), f, cell)) {
					call_list->assign(f);
					fail = false;
					occupied.insert(f);
					break;
				}
			}
		}
		options->Log() << area->calls[call_list->getCurrent()];
	}
	options->Log() << std::endl;
}

/** Operator obraceneho aritmetickeho porovnani.
 */
struct GreaterThan {
	/** Srovnava hodnoty v obracenem poradi.
	 * \param a prvni hodnota
	 * \param b druha hodnota
	 * \return true, pokud je prvni hodnota vetsi nez druha
	 */
	bool operator()(int a, int b) const {
		return a > b;
	}
};

// Smallest acceptable most heavily occupied frequency
/** Vyber nejmensi z nejvice vyuzitych frekvenci.
 * \param call_list setrideny seznam vysilacu
 */
void SequentialAlgorithm::frequencyHeaviestOccupied(CallList * call_list) {
	std::map<int, int, GreaterThan> occupied;
	while (call_list->getNext()) {
		options->Log() << std::setw(5) << call_list->getCurrent() << "=";
		bool fail = true;
		int cell = area->findCell(call_list->getCurrent());
		int occupy = 0;
		/* try to assign the most heavily occupied frequency - if more, than the smallest of them */
		for (std::map<int, int, GreaterThan>::iterator f = occupied.begin(); f != occupied.end(); ++f) {
			if (area->assignCall(call_list->getCurrent(), f->second, cell)) {
				call_list->assign(f->second);
				fail = false;
				/* increase the count of the antenas with this frequency */
				occupy = f->first / frequencies;
				int freq = f->second;
				occupied.erase(f);
				occupied[(occupy + 2) * frequencies - freq] = freq;
				break;
			}
		}
		/* if no occupied frequency available, assign the smallest acceptable */
		if (fail) {
			for (int f = 1; f <= frequencies; ++f) {
				if (area->assignCall(call_list->getCurrent(), f, cell)) {
					call_list->assign(f);
					fail = false;
					/* insert the current frequency to the occupied list */
					occupied[2 * frequencies - f] = f;
					break;
				}
			}
		}
		options->Log() << area->calls[call_list->getCurrent()] << "(" << occupy + 1 << ")";
	}
	options->Log() << std::endl;
}
